package com.littrabble.sort;

public class Quick {

	public static void sort(int[] data, int n, int left, int right) {

		if (left <= right) {
			int k = partition(data, left, right, n);
			sort(data, n, left, k - 1);
			sort(data, n, k + 1, right);
		}
	}

	public static int partition(int[] data, int left, int right, int n) {

		int pivot = data[left];
		int i = left;
		int j = right + 1;
		int tmp;

		while (true) {
			while (++i <= right && data[i] < pivot);
			while (--j >= left && data[j] > pivot);

			if (i < j) {
				tmp = data[i];
				data[i] = data[j];
				data[j] = tmp;
			} else {
				break;
			}
		}

		data[left] = data[j];
		data[j] = pivot;

		return j;
	}
}
